package com.gitee.huxing.algorithmic.daily;

import com.gitee.huxing.algorithmic.stack.Solution;

import java.util.*;

/**
 * @Description: 外星文字典
 * 现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
 *
 * 给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
 *
 * 请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
 *
 * 字符串 s 字典顺序小于 字符串 t 有两种情况：
 *
 * 1. 在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么s 的字典顺序小于 t 。
 * 2. 如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
 *
 * @ProjectName: algorithmic-pactice
 * @Package: AlienOrder
 * @ClassName: AlienOrder
 * @Author: huxingmale
 * @DateTime: 2022-05-31 8:40
 */
public class AlienOrder {

    public static void main(String[] args) {
        System.out.println(new AlienOrder().alienOrder(new String[]{"wrt","wrf","er","ett","rftt"}));
    }
    static final int VISITING = 1, VISITED = 2;
    Map<Character, List<Character>> edges = new HashMap<Character, List<Character>>();
    Map<Character, Integer> states = new HashMap<Character, Integer>();
    boolean valid = true;
    char[] order;
    int index;

    public String alienOrder(String[] words){
        int length = words.length;
        for (String word : words){
            int wordLength = word.length();
            for (int j = 0; j < wordLength; j++){
                char c = word.charAt(j);
                edges.putIfAbsent(c, new ArrayList<Character>());
            }
        }
        for (int i = 1; i < length && valid; i++){
            addEdge(words[i - 1], words[i]);
        }
        order = new char[edges.size()];
        index = edges.size() - 1;
        Set<Character> letterSet = edges.keySet();
        for (char u : letterSet){
            if (!states.containsKey(u)){
                dfs(u);
            }
        }
        if (!valid){
            return "";
        }
        return new String(order);
    }

    public void addEdge(String before, String after){
        int length1 = before.length(), length2 = after.length();
        int length = Math.min(length1, length2);
        int index = 0;
        while (index < length){
            char c1 = before.charAt(index), c2 = after.charAt(index);
            if (c1 != c2){
                edges.get(c1).add(c2);
                break;
            }
            index++;
        }
        if (index == length && length1 > length2){
            valid = false;
        }
    }
    public void dfs(char u){
        states.put(u, VISITING);
        List<Character> adjacent = edges.get(u);
        for (char v : adjacent){
            if (!states.containsKey(v)){
                dfs(v);
                if (!valid){
                    return;
                }
            } else if (states.get(v) == VISITING){
                valid = false;
                return;
            }
        }
        states.put(u, VISITED);
        order[index] = u;
        index--;
    }
}
